package code1.graph;

import java.util.LinkedList;
import java.util.Queue;

public class P1020 {

    //思路：从边界出发，找出所有能到达的陆地单元格并统计数量；用总陆地数减去能到达边界的单元格数即为所求

    int n,m;
    boolean[][] visited;
    int[][] go={{1,0},{-1,0},{0,-1},{0,1}};

    //bfs搜索出从(x,y)出发能到达的陆地单元格数量
    int bfs(int x,int y,int[][] grid){
        Queue<int[]> queue=new LinkedList<>();
        visited[x][y]=true;
        queue.offer(new int[]{x,y});
        int cnt=1;
        while(!queue.isEmpty()){
            int[] point = queue.poll();
            for(int i=0;i<4;i++){
                int nextx=point[0]+go[i][0];
                int nexty=point[1]+go[i][1];
                if(nextx>=0 && nextx<n && nexty>=0 && nexty<m && grid[nextx][nexty]==1 && !visited[nextx][nexty]){
                    visited[nextx][nexty]=true;
                    queue.offer(new int[]{nextx,nexty});
                    cnt++;
                }
            }
        }
        return cnt;
    }

    public int numEnclaves(int[][] grid) {
        n=grid.length;
        m=grid[0].length;
        visited=new boolean[n][m];
        int total=0;
        //统计总陆地数
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j]==1){
                    total++;
                }
            }
        }
        //从边界上的单元格出发,统计能到的陆地单元格的总数
        int count=0;
        for(int i=0;i<m;i++){
            if(!visited[0][i] && grid[0][i]==1){
                int cnt=bfs(0,i,grid);
                count+=cnt;
            }
            if(!visited[n-1][i] && grid[n-1][i]==1){
                int cnt=bfs(n-1,i,grid);
                count+=cnt;
            }
        }
        for(int i=0;i<n;i++){
            if(!visited[i][0] && grid[i][0]==1){
                int cnt=bfs(i,0,grid);
                count+=cnt;
            }
            if(!visited[i][m-1] && grid[i][m-1]==1){
                int cnt=bfs(i,m-1,grid);
                count+=cnt;
            }
        }
        return total-count;
    }
}
